package cn.kent.middle;

import java.util.*;

/**
 * 17. 电话号码的字母组合
 */
public class LetterCombinations {
    private static final Map<Character,String> map = new HashMap<>();
    List<String> ans = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    String digits;
    int len;

    static {
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
    }

    public List<String> letterCombinations(String digits) {
        this.len = digits.length();
        if(len == 0) {
            return ans;
        }
        this.digits = digits;
        dfs(0);
        return ans;
    }

    public void dfs(int index) {
        if(index == len) {
            ans.add(sb.toString());
            return;
        }
        char ch = digits.charAt(index);
        String choices = map.get(ch);
        int choicesLen = choices.length();
        for(int i=0; i<choicesLen; i++) {
            char choice = choices.charAt(i);
            sb.append(choice);
            dfs(index+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
